//: [Previous](@previous)
/*:
 
 #2 [Add Two Numbers](https://leetcode.com/problems/add-two-numbers/description/)
 
 You are given two **non-empty** linked lists representing two non-negative integers. The digits are stored in **reverse order** and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
 
 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
 
 You may assume the two numbers do not contain any leading zero, except the number 0 itself.
 
 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 
 Example:
 
 ```
 Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 Output: 7 -> 0 -> 8
 Explanation: 342 + 465 = 807.
 ```
 
 T: O(n)
 S: O(1)
 */
import Foundation

class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        let dynamicHead: ListNode = ListNode(-1)
        var tmp1: ListNode? = l1
        var tmp2: ListNode? = l2
        var cur: ListNode = dynamicHead
        var carrid = 0
        
        while tmp1 != nil || tmp2 != nil || carrid != 0 {
            let num1 = tmp1?.val ?? 0
            let num2 = tmp2?.val ?? 0
            let sum = num1 + num2 + carrid
            cur.next = ListNode(sum%10)
            carrid = sum / 10
            
            tmp1 = tmp1?.next
            tmp2 = tmp2?.next
            cur = cur.next!
        }
        return dynamicHead.next
    }
}

var node1 = ListNode(2)
node1.next = ListNode(4)
node1.next?.next = ListNode(3)
var node2 = ListNode(5)
node2.next = ListNode(6)
node2.next?.next = ListNode(4)

print("(\(node1)) + (\(node2)) = (\(String(describing: Solution().addTwoNumbers(node1, node2))))")

//: [Next](@next)
